Fixpoint G n := match n
 | 0 => 1
 | S n' => match n'
             | 0 => 3
             | S n'' => match n''
                          | 0 => 9
                          | S n''' => G n' + 3 * G n'' + 3 * G n'''.